Distance entre deux sommets

Définition   Distance entre deux sommets sur un graphe non orienté

Soit  \(G\) un graphe non orienté de matrice d’adjacence \(A\) . La distance entre deux sommets distincts  \(i\) et  \(j\) de ce graphe est le plus petit entier  \(k\) tel que le terme d’indice  \(i,j\) de la matrice  \(A^k\) soit non nul.

Remarque

On peut supprimer l’hypothèse  \(i\) et  \(j\) distincts car, par convention,  \(A^0\) est une matrice identité,
donc on trouve une distance nulle entre un sommet et lui-même.